#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 需要提前一化和插入#
void mancher(const string &s, int rad[])
{
    for (int i = 1, l = 1, r = 0; i < s.size(); i++)
    {
        int k = (i > r) ? 1 : min(rad[l + r - i], r - i + 1);
        while (1 <= i - k && i + k < s.size() && s[i - k] == s[i + k])
        {
            k++;
        }
        rad[i] = k--;
        if (i + k > r)
        {
            l = i - k;
            r = i + k;
        }
    }
}